#include <bits/stdc++.h>
using namespace std;

/*
2845. 统计趣味子数组的数目
已解答
中等
相关标签
相关企业
提示
给你一个下标从 0 开始的整数数组 nums ，以及整数 modulo 和整数 k 。

请你找出并统计数组中 趣味子数组 的数目。

如果 子数组 nums[l..r] 满足下述条件，则称其为 趣味子数组 ：

在范围 [l, r] 内，设 cnt 为满足 nums[i] % modulo == k 的索引 i 的数量。并且 cnt % modulo == k 。
以整数形式表示并返回趣味子数组的数目。

注意：子数组是数组中的一个连续非空的元素序列。

 

示例 1：

输入：nums = [3,2,4], modulo = 2, k = 1
输出：3
解释：在这个示例中，趣味子数组分别是： 
子数组 nums[0..0] ，也就是 [3] 。 
- 在范围 [0, 0] 内，只存在 1 个下标 i = 0 满足 nums[i] % modulo == k 。
- 因此 cnt = 1 ，且 cnt % modulo == k 。
子数组 nums[0..1] ，也就是 [3,2] 。
- 在范围 [0, 1] 内，只存在 1 个下标 i = 0 满足 nums[i] % modulo == k 。
- 因此 cnt = 1 ，且 cnt % modulo == k 。
子数组 nums[0..2] ，也就是 [3,2,4] 。
- 在范围 [0, 2] 内，只存在 1 个下标 i = 0 满足 nums[i] % modulo == k 。
- 因此 cnt = 1 ，且 cnt % modulo == k 。
可以证明不存在其他趣味子数组。因此，答案为 3 。
示例 2：

输入：nums = [3,1,9,6], modulo = 3, k = 0
输出：2
解释：在这个示例中，趣味子数组分别是： 
子数组 nums[0..3] ，也就是 [3,1,9,6] 。
- 在范围 [0, 3] 内，只存在 3 个下标 i = 0, 2, 3 满足 nums[i] % modulo == k 。
- 因此 cnt = 3 ，且 cnt % modulo == k 。
子数组 nums[1..1] ，也就是 [1] 。
- 在范围 [1, 1] 内，不存在下标满足 nums[i] % modulo == k 。
- 因此 cnt = 0 ，且 cnt % modulo == k 。
可以证明不存在其他趣味子数组，因此答案为 2 。
 

提示：

1 <= nums.length <= 105 
1 <= nums[i] <= 109
1 <= modulo <= 109
0 <= k < modulo
*/

// 法一
class Solution {
public:
	using ll = long long;
	long long countInterestingSubarrays(vector<int>& nums, int modulo, int k) {
		ll count = 0;
		unordered_map<int, ll> prefixCout;
		prefixCout[0] = 1;  // 从开始到当前位置的子数组
		int curCount = 0;

		for (int num : nums) {
			// num % modulo == k 就++curCount
			if (num % modulo == k)  curCount++;
			// 需要查找是否存在之前的 prefixCount，使得 (curCount - prefixCount) % modulo == k
			int tar = (curCount - k) % modulo;
			if (tar < 0)    tar += modulo;  // 防止负数

			// 已经有tar 符合
			count += prefixCout[tar];
			// 更新 prefixCount, 记录当前 curCount % modulo 次数
			prefixCout[curCount % modulo]++;
		}
		return count;
	}
};

// 法二
class Solution {
	public:
	long long countInterestingSubarrays(vector<int>& nums, int modulo, int k) {
		int n = nums.size(); // 获取数组的长度
		vector<int> sum(n + 1); // sum[i]表示从 nums[0] 到 nums[i-1] 中，满足 nums[i-1] % modulo == k 的元素的个数
		// 计算前缀和：sum[i] 表示 nums[0] 到 nums[i-1] 中满足 nums[j] % modulo == k 的元素的个数
		for (int i = 0; i < n; i++) {
			sum[i + 1] = sum[i] + (nums[i] % modulo == k); // 如果 nums[i] % modulo == k，则将 sum[i+1] 加 1
		}
		vector<int> cnt(min(n + 1, modulo)); // cnt 数组用于记录前缀和 mod 模后的出现次数
		long long ans = 0; // 用于保存符合条件的趣味子数组的总数
		// 遍历前缀和数组 sum
		for (int s : sum) {
			// 如果当前前缀和 s 大于等于 k，表示我们有可能找到符合条件的子数组
			if (s >= k) {
				// 根据公式 (sum[r] - sum[l]) % modulo == k 计算出符合条件的子数组数量
				ans += cnt[(s - k) % modulo]; // 查找之前满足条件的前缀和
			}
			// 更新前缀和的 mod 值出现次数
			cnt[s % modulo]++; // 记录当前前缀和的 mod 值出现次数
		}
		return ans; // 返回符合条件的趣味子数组的数量
	}
};